Audit logs have long been used to keep permanent records of critical events. The basic idea is that the audit log can be used at some future date to reconstruct events that happened in the past. This reconstruction might be required for legal purposes (to determine who did what when), for accounting purposes, or to reconstruct things after a disaster: errors, loss of data, deliberate sabotage, etc.
Traditionally, audit logs have been kept on paper. For example: 1) Account holders in banks were given bank books that log entries of every transaction in the account: deposits, withdrawals, and interest accrual; 2) Many cash registers print a record of every transaction on a paper tape inside the machine; 3) Notary publics in some jurisdictions keep a paper log listing all documents they have notarized; and 4) Many companies have logbooks where visitors sign their names upon entry into the premises.
Audit logs are more useful if the entries can be authenticated in some way. That is, there should be no way for a person to undetectably modify the audit log after the fact. There should be no way for a person to add backdated entries into the log, delete entries from the log, or modify entries already in the log. In the paper systems listed above, the physical log itself (either a single piece of paper or a bound book) enforces this authentication. If every cash register transaction is printed, one after the other, on a long spool of paper tape, someone cannot modify the log entries for past transactions. If a company's visitors log consists of a single bound book with sequential entries, someone cannot add or delete a name without being noticed.
Many modern audit logs are often kept in digital files on computer. Examples of such computer audit logs include but are not limited to: 1) a computer logging network access and other activity; 2) a door entry system that logs the entry/exit of people into/from a secure area; 3) a secure digital camera that needs to guarantee the authenticity of pictures it has taken; and 4) an electronic wallet (e.g., a smart card, a portable network computer, a PC dongle, or even a digital file). Such computer audit logs differ from paper documents in that they can be modified undetectably. For example, it is easy to read a computer file containing an audit log from a disk, add, delete, and modify individual entries at will, and write that file back to disk in such a way that the changes will go undetected. Computer files often contain information about when they were last modified, but this information is not secure and can be easily falsified. In fact, many computer hackers who break into computer systems take specific actions to modify the computers' audit logs to erase all traces of their actions.
Computer security manufacturers have responded to this threat in several ways. One is to force the audit log to be continuously printed out on paper. This is a common technique, described in Clifford Stoll's book "The Cuckoo's Egg." Variants of this technique involve writing the audit log to a non-erasable medium, such as a CD-ROM, or to a magnetic tape machine with no rewind capabilities. Sometimes the entire contents of a computer disk is saved to backup tape, and that tape is stored off-line for audit purposes.
Another approach uses conventional computer security techniques to guard the audit log files. Such techniques include hiding the log files, encrypting them, requiring special permissions to write to them, etc. These techniques work well in some applications--most notably when the audit log is stored on a shared computer and the malicious person trying to modify the audit log does not have full permissions on that computer--but are not without their problems. For example, clever hackers can often figure out ways around the computer security techniques and make changes to the audit log.
Another disadvantage of conventional techniques is that they do not work when the software creating the audit log does not trust the machine or network it is running on. This situation might occur when a Java-like Internet application is running on an unsecured remote machine or over an insecure network, when a software "agent" is running on a remote computer, or when a piece of software is running on a hardware device whose tamper-resistance features are not reliable.
One solution to the untrusted machine problem is disclosed in U.S. Pat. No. 5,136,646 for applications where a sequence of files is continuously being generated. The solution involves writing a hash of an immediately preceding file into each current file. In this way, each file is chained to a temporal sequence of all its predecessors, such that an attacker modifying any file must also modify all of its predecessors in the chain to avoid detection. This increases, but does not eliminate the likelihood of a successful attack. Furthermore, such an attack will destroy the security of every file in the chain, in addition to the particular file targeted for attack. Like most systems, the security ultimately rests on safeguarding one or more cryptographic keys (e.g., a message encryption/decryption key or an authentication key used in a keyed hash). This poses an especial problem when sensitive information must be kept on an untrusted machine ("U") that is not physically secure or sufficiently tamper-resistant to guarantee that it cannot be taken over by some attacker.
One solution to the untrusted machine problem is to maintain secure communication with a trusted machine ("T"). In particular, if there is a reliable, high-bandwidth channel constantly available between U and T, then the security of information on U is easily guaranteed. U need only encrypt the information as it is created and transmit it to T over the channel. The information is then stored in an audit log on T, in a secure form safe from attack.
A few moments' reflection will reveal that no security measure (including the channel to T) can protect audit log (also called a "logfile") entries written after an attacker has gained control of U. At that point, U will write to the log whatever the attacker wants it to write. This problem arises, for example, where a common encryption key is used for multiple information entries. However, it is possible is to refuse the attacker the ability to read, alter, or delete log entries made before he compromised the logging machine by using signed Diffie-Hellman key exchange and exchanging new keys every few minutes.
Thus, using Diffie-Hellman key exchange to communicate with a trusted machine over a reliable, high-bandwidth, continuously available channel is a preferred solution to situations where information must be kept on a unsecured machine. Unfortunately, such an ideal communications channel is often unavailable. In a system lacking such an ideal communications channel, we nevertheless would like to be able to:
1) ensure that an attacker who gains control of U at time t will not be able to read log entries made before time t; PA1 2) ensure that the attacker will not be able to undetectably alter or delete log entries, made prior to time t, after U reports its results back to T; and PA1 3) provide for occasional "commitments" from U, specifying the current values of its logs in a way that will not allow any later changes to be undetectably made, even if U is compromised.